package com.yusong.algorithm.dp;

import java.util.LinkedList;
import java.util.List;

public class Merge315 {

    public static void main(String[] args) {

        Merge315 main= new Merge315();
        int[] para = {2,0,1};
        main.countSmaller(para);
    }


    /**
     动态规划
     向右边遍历，找到小于该数的第一个数字，遍历数 + 值
     **/
    public List<Integer> countSmaller(int[] nums) {
        int length = nums.length;
        List<Integer>  res = new LinkedList<>();
        if(length > 0){
            res.add(new Integer(0));
        }
        for(int i = (length-2); i >= 0;i--){
            int thisTime = 0;
            int thisNum = nums[i];
            int index = 0;
            int big = 1;
            for(int j = i+1; j < length; j++){
                if(thisNum > nums[j]){
                    System.out.println(thisNum+ "_"+ nums[j]);
                    int thisTimeNow = res.get(index) +big;
                    if(thisTimeNow > thisTime){
                        thisTime = thisTimeNow;
                    }

                    if(thisTime >= (length - j + 1)){
                        break;
                    }
                    big++;
                }
                index++;
            }
            res.add(0, thisTime);
        }
        return res;
    }

}
